package com.camus.algorithm.impl;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import com.camus.algorithm.SubsetAlgorithm4Int;

/**
 * 简单递归算法求目标和的子集
 * 
 * @author jie.deng
 *
 */
public class SubsetAlgorithmOfRecursion4Int2 implements SubsetAlgorithm4Int {

	private static final Logger log = LoggerFactory.getLogger(SubsetAlgorithmOfRecursion4Int2.class);

	@Override
	public int[] findSubsetOfTargetSum(int[] candidateArr, int target) {
		counter.remove();

		Deque<Integer> queue = new ArrayDeque<>();
		// 逐层递归
		int[] subsetArr = findSubsetOfTargetSum(candidateArr, 0, queue, target);

		log.info("入参paramArr={},target={},resultArr={},时间复杂度={}", Arrays.toString(candidateArr), target, subsetArr,
				counter.get());
		return subsetArr == null || subsetArr.length == 0 ? null : subsetArr;
	}

	/**
	 * 
	 * @param candidateArr
	 * @param candidateIdxBegin
	 * @param selectedIdxQueue
	 * @param remain
	 * @return
	 */
	public int[] findSubsetOfTargetSum(int[] candidateArr, int candidateIdxBegin, Deque<Integer> selectedIdxQueue,
			int remain) {
		counter.set(counter.get().intValue() + 1);
		// 1.递归终止条件
		if (remain == 0) {
			return filterSubset(candidateArr, selectedIdxQueue);
		}
		if (candidateIdxBegin >= candidateArr.length) {
			return null;
		}

		int len = candidateArr.length;
		// 2.当前层逻辑：可以在[candidateIdxBegin,len)中选择一个
		for (int i = candidateIdxBegin; i < len; i++) {
			selectedIdxQueue.offerLast(i);
			// 3.递归调用下一层
			int[] arr = findSubsetOfTargetSum(candidateArr, i + 1, selectedIdxQueue, remain - candidateArr[i]);
			if (arr != null) {
				return arr;
			}
			// 4.回溯
			selectedIdxQueue.pollLast();
		}
		return null;
	}

	private int[] filterSubset(int[] candidateArr, Deque<Integer> selectedIdxQueue) {
		int len = selectedIdxQueue.size();
		if (len == 0) {
			return null;
		}
		int[] subsetArr = new int[len];
		int idx = 0;
		while (!selectedIdxQueue.isEmpty()) {
			subsetArr[idx++] = candidateArr[selectedIdxQueue.pollFirst().intValue()];
		}
		return subsetArr;
	}

}
